package 力扣;
//给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
//按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
//    "123"
//    "132"
//    "213"
//    "231"
//    "312"
//    "321"
//给定 n 和 k，返回第 k 个排列。

import java.util.ArrayList;
import java.util.List;

public class 排列序列 {
    public static void main(String[] args) {
        String s = getPermutation(3, 2);
        System.out.println(s);
    }
    public static String getPermutation(int n, int k) {
        boolean[] used = new boolean[n+1];//记录当前的索引的数是否被使用过
        return dfs(n, new ArrayList<String>(), used, 0,k);
    }
    private static String dfs(int n, List<String> levelList, boolean[] used, int depth,int k) {
        if (depth == n) {//触发出口条件，开始收集结果集
            StringBuilder res = new StringBuilder();
            for (String s : levelList)
                res.append(s);
            return res.toString();
        }
        int cur = factorial(n - depth - 1);//当前的depth也就是索引，有多少排列数
        for (int i = 1; i <=n; i++) {
            if (used[i])
                continue;//当前元素被使用过，做剪枝
            if (cur < k) {//当前的排列组合数小于k，说明就算这一层排完了，也到不了第k个，剪枝
                k -= cur;
                continue;
            }
            levelList.add(i+ "");//list收的是string类型
            used[i] = true;//当前元素被使用过标记
            return dfs(n, levelList, used, depth + 1,k);
        }
        return null;
    }

    //返回n的阶乘，如3!=3*2*1=6
    private static int factorial(int n) {
        int res = 1;
        while (n > 0) {
            res *= n--;
        }
        return res;
    }
    }
